package com.neuedu.queue;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 单向环形带哨兵链表实现
 * 提示：构造方法中有重复代码，可以将次代码放在初始化块中。{}
 * 主要注意3点：
 *      1.新加入元素的next
 *      2.tail的next
 *      3.tail指针的位置
 * @param <E>
 */
public class LinkedListQueue<E> implements Queue<E> , Iterable<E> {

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> cur = head.next;
            @Override
            public boolean hasNext() {
//                return cur != head;  //自己写的待验证
                return cur != null;
            }

            @Override
            public E next() {
                E value = cur.value;
                cur = cur.next;
                return value;
            }
        };
    }


    private static class Node<E> {
        private Node next;
        private E value;

        public Node(Node next, E value) {
            this.next = next;
            this.value = value;
        }
    }

    //单向环形链表无元素时，头尾指针全在哨兵。尾指针的next，指向头。(环)
    private Node<E> head = new Node<>(null,null);//头指针就是哨兵，它不动
    private Node<E> tail = head;//尾指针
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;//容量初始化，可在构造方法中进行设置

    {
        tail.next = head;
    }

    public LinkedListQueue() {
//        tail.next = head;
    }

    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
//        tail.next = head;
    }

    /**
     * 尾部添加元素
     * 因为是单向环形链表，无法让上一节点指向下一节点，只能让当前节点指向下一节点。
     * 例如：1->2 新加入3 ，你可以让3->1,但是无法让2->3.所以这时候就需要引入tail指针，它来完成。
     * 因为tail指向的就是2，tail的next就是2的next，next完成后，tail在再次向后移动。
     * @param value 待插入值
     * @return
     */
    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        Node<E> added = new Node<>(head,value);
        tail.next = added;//以前不理解的地方 (说白了就是起连接作用的)
        tail = added;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        Node<E> removed = head.next;
        head.next = removed.next;
        if (removed == tail){
            head = tail;
        }
        size--;
        return removed.value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        Node<E> first = head.next;
        return first.value;
    }

    @Override
    public boolean isEmpty() {
//        return head == tail;  自己写的(待验证)
        return head.next == null;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }


}
